package leetcode.editor.cn.q1_300.q50;

/**
 * 有点思路，和 84 很像，但是还是看了答案才做出来
 *
 * @author qidi
 * @date 2021-12-22 16:29:37
 */
class Q0085_MaximalRectangle {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            int rows = matrix.length;
            int cols = matrix[0].length;

            int[][] width = new int[rows][cols];


            for (int i = 0; i < rows; i++) {
                int w = 0;
                for (int j = 0; j < cols; j++) {
                    if (matrix[i][j] == '0') {
                        w = 0;
                    } else {
                        w++;
                    }
                    width[i][j] = w;
                }
            }

            int maxArea = 0;

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (width[i][j] == 0) continue;
                    if (i == 0) {
                        maxArea = Math.max(maxArea, width[i][j]);
                    } else {
                        int h = i;
                        int minW = cols;
                        while (h >= 0) {
                            if (width[h][j] == 0) break;
                            minW = Math.min(minW, width[h][j]);
                            maxArea = Math.max(maxArea, minW * (i - h + 1));
                            h--;
                        }
                    }
                }
            }

            return maxArea;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0085_MaximalRectangle().new Solution();
//        System.out.println(solution.maximalRectangle(new char[][]{
//                {'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}
//        }));
        System.out.println(solution.maximalRectangle(new char[][]{
                {'0', '1', '1', '1', '1', '1', '1', '0', '1'}
        }));
    }
}